#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include <limits.h>

using namespace std;

int findKth(int A[], int lenA, int B[], int lenB, int k)
{
    if (k > lenA + lenB) return 0;
    if (lenA == 0) return B[k-1];
    if (k == 1) return min(A[0], B[0]);
    if (lenA > lenB) return findKth(B, lenB, A, lenA, k);
    int indexA = min(lenA, k/2);
    int indexB = k - indexA;
    if (A[indexA-1] <= B[indexB-1]) return findKth(A+indexA, lenA-indexA, B, lenB, k - indexA);
    else return findKth(A, lenA, B+indexB, lenB - indexB, k - indexB);
}


int main(int argc, char **argv)
{
    int A[] = {2,5,7,9,13,15,19,25,29};
    int B[] = {5,7,14,18,23,35,67};
    for (int i = 1; i <= (sizeof(A) + sizeof(B))/sizeof(int); i++)
        cout << i << "element: " << findKth(A, sizeof(A)/sizeof(int), B, sizeof(B)/sizeof(int), i) << endl;
}
